Problema omului care n-are ce face
Concursul de programare Lugoj, martie 1997
Clasa XI-XII
Dificultate: C2

Un om avea un graf si un poligon regulat. Se intampla ca numarul de noduri ale 
grafului coincidea cu numarul de varfuri ale pligonului.
Invartind graful pe toate partile, ce s-a gandit ? Sa amplaseze nodurile grafului
in varfurile poligonului regulat si sa traseze muchiile.
Problema era prea simpla si atunci a complicat-o. A incercat sa amplaseze nodurile
astfel ca suma lungimilor muchiilor (ca laturi sau diagonale ale poligonului) sa
fie minima.
Probabil inca mai lucreaza.
Incercati sa il ajutati.
Omul va va trimite datele intr-un fisier al carui nume se va citi de la tastatura.
Prima linie va contine numarul n de noduri, fiecare nod fiind identificat printr-un
numar de la 1 la n (n<=15). Liniile urmatoare contin fiecare cate o pereche de forma
i j
reprezentand muchia (i,j).
Raspunsul dv va fi afisat pe ecran in forma:
nr-nod-in-graf - nr-de-ordine-al-varfului-in-poligon
pentru fiecare din cele n noduri, pe cate o linie continand suma ungimilor muchiilor.
Observatie: Bietul om avea poligonul obtinut prin reprezentarea iin planul complex a
solutiilor ecuatiei x^n=1.

